class Solution:
  def getLeastNumbers(self, arr: list, k: int) -> list:
    if not arr:
      return []
    def adjust_heap(arr: list, heap_size: int, i: int):
      largest = i
      l = 2 * i + 1
      r = 2 * i + 2
      if l < heap_size and arr[l] > arr[largest]:
        largest = l
      if r < heap_size and arr[r] > arr[largest]:
        largest = r
      if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        adjust_heap(arr, heap_size, largest)
    # 建立大顶堆
    for i in range(len(arr) // 2 - 1, -1, -1):
      adjust_heap(arr, len(arr), i)
    # 交换元素，不断调整大顶堆
    for i in range(len(arr) - 1, 0, -1):
      arr[i], arr[0] = arr[0], arr[i]
      adjust_heap(arr, i, 0)
    return arr[:k]
        

'''
STATUS: SOLVED
TRIES:  1
TIME:   672 MS
MEMORY: 14.9 MB
'''
if __name__ == "__main__":
  solution = Solution()
  res = solution.getLeastNumbers([1], 1)
  print(res)
